package 我的Java学习_算法基础.day_02;

public class _027_旋转数组的最小数字 {
    public static void main(String[] args) {
        int[] a={5,1,2,3,4};
        int[] b={2,3,4,5,6};
        int[] c={1,1,1,0,1};
        int[] d={1,0,1,1,1};    //中间元素和两侧相等，算法失效，用顺序扫描法
        int min = min(a);
        System.out.println(min);
        System.out.println(min(b));
        System.out.println(min(c));
        System.out.println(min(d));

    }

    /**
     *
     * @param array 递增数组的一次旋转数组
     * @return  数组中的最小元素
     */
    static int min(int[] array){
        int begin=0;
        int end=array.length-1;
        //考虑没有旋转这种特殊的旋转
        if(array[begin]<array[end]) return array[begin];
        //begin和end指向相邻元素，退出
        while(begin+1<end){
            int mid = begin +((end-begin)>>1);
            //要么左侧有序，要么右侧有序
            if(array[mid]>=array[begin]){//左侧有序,最小值在无序的那边
                begin=mid;
            }else{
                end=mid;
            }

        }
        return array[end];
    }
}
